package Aleehot100;

/**
 * ClassName: c048
 * Package: Aleehot100
 * Description: 437. 路径总和 III  前缀树的方案待实现，目前是只实现了简单的递归的版本
 *
 * @Author BCXJ
 * @Create 2025/7/18 09:06
 * @Version 1.0
 * @Since 1.0
 */
public class c048 {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode31 = new TreeNode(3);
        TreeNode treeNode32 = new TreeNode(3);
        TreeNode treeNodef2 = new TreeNode(-2);
        TreeNode treeNodef3 = new TreeNode(-3);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode11 = new TreeNode(11);
        TreeNode treeNode10 = new TreeNode(10);

        treeNode10.left = treeNode5;
        treeNode10.right = treeNodef3;
        treeNode5.left = treeNode31;
        treeNode5.right = treeNode2;
        treeNode31.left = treeNode32;
        treeNode31.right = treeNodef2;
        treeNode2.right = treeNode1;
        treeNodef3.right = treeNode11;

        System.out.println(pathSum(treeNode10, 8));

    }
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    static int res = 0;
    public static int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        res = 0;
        int process = process(root, targetSum, 0);
        int l = pathSum(root.left, targetSum);
        int r = pathSum(root.right, targetSum);
        System.out.println(root.val + " " + l + " " + r + " " + process);
        return l + r + process;
    }

    private static int process(TreeNode root, long targetSum, long cur) {
        int res = 0;
        if(root == null) {
            return 0;
        }
        if(targetSum == cur + root.val) {
            res++;
        }
        res += process(root.left, targetSum, cur + root.val);
        res += process(root.right, targetSum, cur + root.val);
        return res;
    }
}
